package com.wangyadong.hobby.schedule.jobtask.dsa.binaryTree;

import com.wangyadong.hobby.schedule.jobtask.LinkedQueue;
import com.wangyadong.hobby.schedule.jobtask.Queue;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class LinkedBinaryTree<E> extends BinaryAbstractTree<E> {
    @Override
    public Iterator<E> iterator() {
        return new ElementIterator();
    }


    public void insert(E e) {
        Node<E> node = createNode(e, null, null, null);
        if (isEmpty()) {
            addRoot(e);
        } else {
             Node<E> current = (Node) root();

            while (current != null) {
                Node<E> nodeParetn = current;
                current = current.getLeft();
                if (current == null) {
                    nodeParetn.setLeft(node);
                    node.setParent(nodeParetn);
                    return;
                }else {
                    current = nodeParetn.getRight();
                    if (current == null) {
                        nodeParetn.setRight(node);
                        node.setParent(nodeParetn);
                        return;
                    }
                }

            }
//            Iterable<Position<E>> positions = positions();
//            Iterator<Position<E>> iterator = positions.iterator();
//            while (iterator.hasNext()) {
//                Position<E> next = iterator.next();
//                children(positions);
//            }


        }

    }


////////////////////////////////////////////////////////////////////////////////

    /**
     * 前序遍历
     *
     * @return
     */
    public Iterable<Position<E>> preOrder() {
        List<Position<E>> snapList = new ArrayList<>();
        preorderSubtree(root(), snapList);
        return snapList;
    }

    /***
     * 后序遍历
     * @return
     */
    public Iterable<Position<E>> postOrder() {
        List<Position<E>> snapList = new ArrayList<>();
        postOrderSubTree(root(), snapList);
        return snapList;
    }


    public Iterable<Position<E>> breadthFirst() {
        List<Position<E>> snapList = new ArrayList<>();
        if (isEmpty()) {
            Queue linkedQueue = new LinkedQueue();
            linkedQueue.enqueue(root);
            while (!linkedQueue.isEmpty()) {
                Position<E> dequeue = (Position<E>) linkedQueue.dequeue();
                snapList.add(dequeue);
                for (Position position : children(dequeue)) {
                    linkedQueue.enqueue(position);
                }
            }
        }
        return snapList;
    }

    public Iterable<Position<E>> inOrder() {
        List<Position<E>> snapList = new ArrayList<>();
        if (!isEmpty()) {
            inOrderSubTree(root(), snapList);
        }
        return snapList;
    }

    ////////////////////////////////////////////////////////////////////////////////

    private class ElementIterator implements Iterator<E> {
        Iterator<Position<E>> posIterator = positions().iterator();

        public boolean hasNext() {
            return posIterator.hasNext();
        }

        public E next() {
            return posIterator.next().getElement();
        } // return element!

        public void remove() {
            posIterator.remove();
        }
    }


    public Node<E> createNode(E e, Node left, Node right, Node parent) {
        return new Node<>(e, left, right, parent);
    }

    @Override
    public Position<E> getElement() {
        return null;
    }

    @Override
    public boolean isRoot(Position position) throws IllegalArgumentException {
        return false;
    }

    @Override
    public Iterable<Position<E>> positions() {
        return inOrder();
    }


    protected Node root = null;
    private int size = 0;

    public LinkedBinaryTree() {
    }

    public int size() {
        return size;
    }


    public Position<E> root() {
        return root;
    }

    public Node vaildate(Position<E> position) {
        if (!(position instanceof Node)) {
            throw new IllegalArgumentException("not vaildate position type");
        }
        Node<E> node = (Node) position;
        if (node == node.getParent()) {
            // 失效节点
            throw new IllegalArgumentException("p is no longer in the tree");
        }
        return node;
    }

    @Override
    public Position parent(Position<E> position) throws IllegalArgumentException {
        Node vaildate = vaildate(position);
        return vaildate.getParent();
    }

    @Override
    public Position<E> left(Position<E> position) throws IllegalArgumentException {
        return vaildate(position).getLeft();
    }

    @Override
    public Position<E> right(Position<E> position) throws IllegalArgumentException {
        return vaildate(position).getRight();
    }

    public Position<E> addRoot(E e) {
        if (!isEmpty()) {
            throw new IllegalStateException("tree is not empty");
        }
        Node<E> node = createNode(e, null, null, null);
        root = node;
        size = 1;
        return node;
    }

    public Position<E> addLeft(Position<E> position, E e) {
        Node vaildate = vaildate(position);
        if (vaildate.getLeft() != null) {
            throw new IllegalArgumentException("");
        }
        Node<E> node = createNode(e, null, null, vaildate);
        vaildate.setLeft(node);
        size++;
        return node;

    }

    public Position<E> addRight(Position<E> position, E e) {
        Node vaildate = vaildate(position);
        if (vaildate.getRight() != null) {
            throw new IllegalArgumentException("tree has right node");
        }

        Node<E> node = createNode(e, null, null, vaildate);
        size++;
        vaildate.setRight(node);
        return node;
    }


    public void attach(Position<E> position,
                       LinkedBinaryTree<Position<E>> linkedBinaryTree1,
                       LinkedBinaryTree<Position<E>> linkedBinaryTree2) {

        Node vaildate = vaildate(position);
        if (isInternal(position)) {
            throw new IllegalArgumentException("p is a internal node");
        }
        if (!linkedBinaryTree1.isEmpty()) {
            linkedBinaryTree1.root.setParent(vaildate);
            vaildate.setLeft(linkedBinaryTree1.root);
            linkedBinaryTree1.root = null;
            linkedBinaryTree1.size = 0;
        }
        if (!linkedBinaryTree2.isEmpty()) {
            linkedBinaryTree2.root.setParent(vaildate);
            vaildate.setRight(linkedBinaryTree2.root);
            linkedBinaryTree2.root = null;
            linkedBinaryTree2.size = 0;
        }
        size = linkedBinaryTree2.size + linkedBinaryTree1.size;

    }

    public void remove(Position<E> position) {
        Node vaildate = vaildate(position);
        if (numChildren(position) == 2) {
            throw new IllegalArgumentException("");
        }
        //
        Node child = vaildate.getLeft() == null ? vaildate.getRight() : vaildate.getLeft();
        if (child != null) {
            child.setParent(vaildate.getParent());
        }
        if (vaildate == root) {
            root = child;
        }
        if (vaildate == vaildate.getParent().getLeft()) {
            vaildate.getParent().setLeft(child);
        } else {
            vaildate.getParent().setRight(child);
        }
        Object element = vaildate.getElement();
        size--;
        vaildate = null;

    }

    public E set(Position<E> position, E e) {
        Node vaildate = vaildate(position);
        E element = (E) vaildate.getElement();
        vaildate.setElement(e);
        return element;
    }


    protected static class Node<E> implements Position<E> {
        private E element;
        private Node<E> left;
        private Node<E> right;
        private Node<E> parent;


        public Node(E element, Node<E> left, Node<E> right, Node<E> parent) {
            this.element = element;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }

        @Override
        public E getElement() {
            return element;
        }

        public void setElement(E element) {
            this.element = element;
        }

        public Node<E> getLeft() {
            return left;
        }

        public void setLeft(Node<E> left) {
            this.left = left;
        }

        public Node<E> getRight() {
            return right;
        }

        public void setRight(Node<E> right) {
            this.right = right;
        }

        public Node<E> getParent() {
            return parent;
        }

        public void setParent(Node<E> parent) {
            this.parent = parent;
        }
    }
}
